package com.leetcode.动态规划;

/**
 * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
 * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
 * （例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
 * 题目数据保证答案符合 32 位带符号整数范围。
 * @author LZF
 *
 */
public class L115不同的子序列 {
	public static void main(String[] args) {
		int result = numDistinct("rabbbit", "rabbit");
		System.out.println(result);
	}
	
	/**
	 * （t在s中出现的个数）
	 * dp[i][j]:t[0,i] 在s[0,j]中出现的个数。t[0,i]表示下标从0到i的字串
	 * dp[i][j]有两种情况得来：当遍历到t[i]时，考虑删不删除s[j]这个元素
	 * 1、删除s[j]（相当于不考虑s[j]这个元素），则dp[i][j]=dp[i][j-1]，根据定义很容易得到
	 * 2、不删除s[j]（相当于将s[j]这个元素进行匹配），则需要进行判断
	 * 	if(t[i] == s[j]) 则 dp[i][j]=dp[i-1][j-1],根据定义解释
	 * 如果t[i] != s[j],那就相当于第一种情况。
	 * 因此就是：if(t[i] == s[j]) dp[i][j]=dp[i-1][j-1] + dp[i][j-1]
	 * 		else dp[i][j]=dp[i][j-1]
	 * 
	 * 初始化：dp[0][0]= t[0]==s[0] ? 1 : 0
	 * 当i>j时，dp[i][j]=0
	 * if(i<=j && i==0 && j>1) dp[0][j]= (t[0]==s[j]) ? dp[0][j - 1] + 1: dp[0][j-1]
	 * 
	 * 1 <= s.length, t.length <= 1000
	 */
	public static int numDistinct(String s, String t) {
		int[][] dp = new int[t.length()][s.length()];
		dp[0][0] = t.charAt(0) == s.charAt(0) ? 1 : 0;
		for(int j = 1;j < s.length();j++) {
			dp[0][j] = t.charAt(0) == s.charAt(j) ? dp[0][j - 1] + 1 : dp[0][j - 1];
		}
		for(int i = 1;i < t.length();i++) {
			for(int j = i;j < s.length();j++) {//这样可以保证j>=i
				if(t.charAt(i) == s.charAt(j))
					dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
				else 
					dp[i][j] = dp[i][j - 1];
			}
		}
		return dp[t.length() - 1][s.length() - 1];
    }
}
